﻿#if 0
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int sum = 0;
        int fmax = 0, fmin = 0;
        int gmax = INT_MIN, gmin = INT_MAX;
        for (auto num : nums) {
            fmax = max(fmax + num, num);
            gmax = max(fmax, gmax);
            fmin = min(fmin + num, num);
            gmin = min(fmin, gmin);
            sum += num;
        }
        return gmin == sum ? gmax : max(gmax, sum - gmin);
    }
}; class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.size() == 1)return nums[0];
        int gt = 1;
        int lt = 1;
        int ret = 0;
        for (auto num : nums) {
            int _gt, _lt;
            if (num < 0) {
                _gt = max(lt * num, num);
                _lt = min(gt * num, num);
            }
            else {
                _gt = max(gt * num, num);
                _lt = min(lt * num, num);
            }
            swap(_gt, gt);
            swap(_lt, lt);
            ret = max(ret, gt);
        }
        return ret;
    }
};
class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int plen = 0, nlen = 0;
        int ret = 0;
        for (auto num : nums) {
            int _plen = plen, _nlen = nlen;
            if (num == 0)_plen = _nlen = 0;
            else if (num < 0) { _nlen = plen + 1; _plen = nlen ? nlen + 1 : 0; }
            else { _plen++; _nlen = nlen ? nlen + 1 : 0; }
            plen = _plen; nlen = _nlen;
            ret = max(ret, plen);
        }
        return ret;
    }
};

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int sz = nums.size();
        if (sz < 3)return 0;
        int ret = 0;
        for (int i = 2; i < sz; i++) {
            int base = i;
            while (i < sz && nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])i++;
            ret += (i - base + 1) * (i - base) / 2;
        }
        return ret;
    }
};
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int sz = arr.size();
        if (sz == 1)return 1;
        vector<int>nums;
        for (int i = 0; i < sz - 1; i++)nums.push_back(arr[i + 1] - arr[i]);
        int pn = 1, nn = 1;
        if (nums[0] > 0)pn = 2;
        if (nums[0] < 0)nn = 2;
        int ret = max(pn, nn);
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > 0) { pn = nn + 1; nn = 1; }
            else if (nums[i] < 0) { nn = pn + 1; pn = 1; }
            else { pn = nn = 1; }
            ret = max(ret, max(pn, nn));
        }
        return ret;
    }
};
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int sz = arr.size();
        int l = 0, r = 0, ret = 1;
        while (r < sz - 1) {
            if (l == r) {
                if (arr[l] == arr[r + 1])l = r + 1;
                r++;
            }
            else {
                if (arr[r] < arr[r - 1] && arr[r] < arr[r + 1])r++;
                else if (arr[r] > arr[r - 1] && arr[r] > arr[r + 1])r++;
                else l = r;
            }
            ret = max(ret, r - l + 1);
        }

        return ret;
    }
};



void* func() {


    return (void*)10;
}

int main() {

    int a = 10;
    int* aa = &a;
    int** aaa = &aa;
    cout << **aaa;
        

    return 0;
}

#include<iostream>
#include<vector>
using namespace std;

int main() {
    vector <vector<int>>vv;
    for (int i = 0; i < 10; i++) {
        vector<int>a{ 1,1,1 };
        vv.push_back(a);
    }
    for (auto& el : vv)
        for (auto num : el)
            cout << num;
                
    return 0;
}
#include<iostream>
#include<string>
using namespace std;

int main() {
    int n = 0;
    cin >> n;
    while (n--) {
        int i, k;
        scanf("%d %d", &i, &k);
        string str;
        cin >> str;
        int j = 0, ret = 0;
        for (auto c : str) {
            if (c == 'W') {
                j++; ret++;
                if (j >= 3)ret += k - 1;
            }
            else { j = 0; ret--; }
        }
        cout << ret << endl;
    }
    return 0;
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        int ret = 0, l = 0, r = -1, sz = arr.size();
        unordered_set<int>hash;
        while (r < sz - 1) {
            ++r;
            while (hash.count(arr[r]) != 0) {
                hash.erase(arr[l++]);
            }
            hash.insert(arr[r]);
            ret = max(ret, r - l + 1);
        }
        return ret;
    }
};  
#include <algorithm>
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n, el; unordered_map<long long int, long long int>hash;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) { cin >> el; hash[el]++; }
    if (n == 1) { cout << el; return 0; }
    vector<pair<long long int, long long int>>nums{ hash.begin(),hash.end() };
    sort(nums.begin(), nums.end(), [&](const pair<long long int, long long int>a, const pair<long long int, long long int>b) {return a.first < b.first; });
    //


    // for(auto el:nums)cout << el.first << ':' << el.second << ' ';
    // cout << endl;
    vector<long long int>dp(nums.size());
    dp[0] = nums[0].first * nums[0].second; dp[1] = nums[1].first * nums[1].second;
    if (nums[0].first + 1 != nums[1].first)dp[1] += dp[0];
    for (int i = 2; i < n; i++) {
        if (nums[i - 1].first + 1 == nums[i].first)
            dp[i] = max(dp[i - 2] + nums[i].first * nums[i].second, dp[i - 1]);
        else
            dp[i] = max(dp[i - 2], dp[i - 1]) + nums[i].first * nums[i].second;
    }
    // // for(auto el:dp)cout << el << ' ';
    // // cout << endl;


    // //
    cout << max(dp.back(), dp[dp.size() - 2]);
}
// 64 位输出请用 printf("%lld")

#include <cmath>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
unordered_map<int, int>myhash;
int n, m;
int check(int mid) {
    int _m = 0;
    for (auto [a, b] : myhash) {
        while (b) {
            b = b - mid >= 0 ? b - mid : 0;
            _m++;
        }
    }
    return m >= _m;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) { int n = 0; cin >> n; myhash[n]++; }
    int maxCount = 0;
    for (auto& [a, b] : myhash)maxCount = max(maxCount, b);
    if (m < myhash.size())cout << -1;
    else {
        int l = 1, r = maxCount;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (check(mid))r = mid;
            else l = mid + 1;
        }
        cout << l;
    }

}
// 64 位输出请用 printf("%lld")
#include <iostream>
#include <queue>
#include<vector>
#include <unordered_map>
using namespace std;
const int N = 2e5 + 1;
int in[N];
int main() {
    unordered_map<int, vector<int>>hash;
    vector<int>ret;
    int n, m;
    cin >> n >> m;
    while (m--) {
        int n1, n2;
        cin >> n1 >> n2;
        hash[n1].push_back(n2);
        in[n2]++;
    }
    queue<int>q;
    for (int i = 1; i <= n; i++)
        if (!in[i])q.push(i);
    while (q.size()) {
        int el = q.front(); q.pop();
        ret.push_back(el);
        for (auto next : hash[el]) {
            if (!(--in[next]))q.push(next);
        }
    }
    // cout << ret.size();
    if (ret.size() == n) {
        for (int i = 0; i < n; i++) {
            cout << ret[i];
            if (i != n - 1)cout << ' ';
        }
    }
    else {
        cout << -1;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串 原串
     * @param arg char字符型vector 需替换数组
     * @return string字符串
     */
    string formatString(string str, vector<char>& arg) {
        // write code here
        int j = 0;
        string ret;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == '%') { ret += arg[j++]; i++; }
            else ret += str[i];
        }
        while (j != arg.size())ret += arg[j++];
        return ret;
    }
};


    

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>>hash{ {-1},{1,3,5,6,7,9},{3,9},{1,2,4,5,7,8,9},{1,3,7,9},{1,3,7,9},{1,7},{1,3,4,5,6,8,9}
    ,{3,7},{1,2,3,4,5,7,8} };
    int ret = 0;
    int a, b;
    cin >> a >> b;
    for (long long int i = a; i <= b; i++) {
        long long int tmp = i;
        int _hash[10] = { 0 };
        while (tmp) {
            int num = tmp % 10;
            tmp /= 10;
            // cout << num << ' ';
            for (int j = 0; j < 10; j++) {
                if (_hash[j] != 0) {
                    for (auto n : hash[num])
                        if (n == j) { ret++; goto next; }
                }
            }
            _hash[num]++;
        }
    next:;
    }
    cout << ret;
}
// 64 位输出请用 printf("%lld")
// 
// 
#include <iostream>
using namespace std;

int main() {
    string str;
    int len = 0;
    cin >> str >> len;
    // cout << len;
    int l = 0, r = 0, para = 0;
    for (r = 0; r < len; r++) {
        if (str[r] == 'G' || str[r] == 'C')para++;
    }
    int left = l, right = r;
    // cout << str[r];
    int _para = para;
    while (r != str.size()) {
        if (str[r] == 'G' || str[r] == 'C')_para++; r++;
        if (str[l] == 'G' || str[l] == 'C')_para--; l++;
        if (_para > para) {
            para = _para;
            left = l;
            right = r;
        }
        // cout << _para << ' ';
        // for(int i = l;i < r;i++)cout << str[i];
        // cout << endl;
    }
    for (int i = left; i < right; i++)cout << str[i];
}


// 64 位输出请用 printf("%lld")


#include <iostream>
using namespace std;

int main() {
    string str;
    int len = 0;
    cin >> str >> len;
    // cout << len;
    int l = 0, r = 0, para = 0;
    for (r = 0; r < len; r++) {
        if (str[r] == 'G' || str[r] == 'C')para++;
    }
    int left = l, right = r;
    // cout << str[r];
    while (r != str.size()) {
 
        int _para = para;
        if (str[r] == 'G' || str[r] == 'C')
            _para++;
        r++;
        if (str[l] == 'G' || str[l] == 'C')
            _para--;
        l++;
        if (_para > para) {
            para = _para;
            left = l;
            right = r;
        }
        cout << _para << ' ';
        for (int i = l; i < r; i++)cout << str[i];
        cout << endl;
    }
    // for (int i = left; i < right; i++)cout << str[i];
}


// 64 位输出请用 printf("%lld")




#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>>hash{ {-1}, {1, 3 , 4 , 6 , 7 ,9}, {3, 9}, {1, 2, 7 ,4, 5, 8}, {1, 3, 7}, {3 ,7 , 9}, {1, 7}, {1, 3 ,4, 5,6,8,9}
        , {3,7,9}, {1, 2 , 5, 7,8} };
    int ret = 0;
    int a = 11, b = 20;
    //cin >> a >> b;
    for (long long int i = a; i <= b; i++) {
        long long int tmp = i;
        int _hash[10] = { 0 };
        while (tmp) {
            int num = tmp % 10;
            tmp /= 10;
            // cout << num << ' ';
            for (int j = 0; j < 10; j++) {
                if (_hash[j] != 0) {
                    for (auto n : hash[num])
                        if (n == j) {
                            ret++;
                             cout << i << ' ';
                            goto next;
                        }
                }
            }
            _hash[num]++;
        }
    next:
        ;
    }
    cout << ':' << ret;
}


#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>>hash{ {-1}, {1, 3 , 4 , 6 , 7 ,9}, {3, 9}, {1, 2, 7 ,4, 5, 8}, {1, 3, 7}, {3 , 9}, {1, 7}, {1, 3 ,4,6,9}
        , {3,9}, {1, 2 , 5, 7,8} };
    int ret = 0;
    int a, b;
    cin >> a >> b;
    for (long long int i = a; i <= b; i++) {
        long long int tmp = i;
        int _hash[10] = { 0 };
        while (tmp) {
            int num = tmp % 10;
            tmp /= 10;
            // cout << num << ' ';
            for (int j = 0; j < 10; j++) {
                if (_hash[j] != 0) {
                    for (auto n : hash[num])
                        if (n == j) {
                            ret++;
                            //  cout << i << ' ';
                            goto next;
                        }
                }
            }
            _hash[num]++;
        }
    next:
        ;
    }
    cout << ret;
}
#include <algorithm>
#include <iostream>
using namespace std;
using LL = long long int;
int main() {
    LL n;
    scanf("%d", &n);
    string str = to_string(n);
    reverse(str.begin(), str.end());
    int ret = 0, i = 1;
    for (auto c : str) {
        int num = c - '0';
        if (num % 2)ret += i;
        i *= 10;
    }
    cout << ret;
}
// 64 位输出请用 printf("%lld")
#include <iostream>
#include <vector>
using namespace std;
using LL = long long int;
int main() {
    LL n, m;
    scanf("%lld %lld", &n, &m);
    vector<vector<LL>>arr(n, vector<LL>(m));
    vector<LL>dx(n), dy(m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%lld", &arr[i][j]);
            dx[i] += arr[i][j];
            dy[j] += arr[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            printf("%lld ", dx[i] + dy[j] - arr[i][j]);
        printf("\n");
    }
}

// 64 位输出请用 printf("%lld")
#include <iostream>
#include <vector>
using namespace std;
using LL = long long int;
int main() {
    LL n, k;
    scanf("%lld %lld", &n, &k);
    vector<LL>posv(n), negv(n);
    for (int i = 0; i < n; i++)
        scanf("%lld", &posv[i]);
    for (int i = 0; i < n; i++)
        scanf("%lld", &negv[i]);
    LL day = 0, _posv = 0, _negv = 0;
    for (int i = 0; i < k; i++) {
        _posv += posv[i];
        _negv += negv[i];
    }
    LL t_posv = _posv, t_negv = _negv;
    for (int i = 0; i < n - k; i++) {
        t_posv += (posv[i + k] - posv[i]);
        t_negv += (negv[i + k] - negv[i]);
        if (t_posv > _posv || (t_posv == _posv && t_negv < _negv)) {
            day = i + 1;
            _posv = t_posv;
            _negv = t_negv;
        }
    }
    printf("%lld", day + 1);
}
// 64 位输出请用 printf("%lld")

int main() {



    return 0;
}
#include <string>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param param string字符串
     * @return string字符串
     */
    string compressString(string param) {
        // write code here
        string ret;
        int time = 0, sz = param.size();
        for (int i = 0; i < sz; i++) {
            time = i;
            while (i < sz && param[i + 1] == param[i])i++;
            ret += param[i];
            if (i - time)ret += to_string(i - time + 1);
        }
        return ret;
    }
};

#include <functional>
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
using LL = long long int;
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    vector<pair<LL, LL>>a(n);
    for (int i = 0; i < n; i++)scanf("%lld", &a[i].first);
    for (int i = 0; i < n; i++)scanf("%lld", &a[i].second);
    sort(a.begin(), a.end(), [&](const pair<LL, LL>a1, const pair<LL, LL>a2) {
        return a1.second == a2.second ? a1.first < a2.first : a1.second > a2.second;
        });
    LL x = 0, y = 0;
    for (int i = 0; i < k; i++) {
        x += a[i].first;
        y += a[i].second;
    }
    printf("%lld %lld", x, y);

}
// 64 位输出请用 printf("%lld")
#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        // write code here
        sort(vw.begin(), vw.end(), [&](const vector<int>& a, const vector<int>& b) {
            return a[1] == b[1] ? a[0] < b[0] : a[1] > b[1];
            });
        int v = 0, w = 0, i = 0;
        while (i < n && v + vw[i][0] <= V) {
            v += vw[i][0];
            w += vw[i][1];
            i++;
        }
        return w;
    }
};

#include<iostream>
#include<vector>
using namespace std;
const int days = 365;
int main() {
    vector<int>hostel = { 1,2,3,4,4,3,2,1 };
    vector<int>cur(hostel);
    for (int i = 1; i <= days; i++) {
        //printf("第%-4d天：", i);
        int num = 0;
        for (int j = 0; j < cur.size();j++) {
            if (!cur[j]--) {
                cur[j] = hostel[j];
                num++;
            }
        }
        printf("%d, ", num);
    }
    return 0;
}
#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    int dp[1010] = { 0 };
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        // write code here
        for (int i = 0; i < n; i++) {
            for (int j = V; j >= vw[i][0]; j--) {
                dp[j] = max(dp[j], dp[j - vw[i][0]] + vw[i][1]);
            }
        }
        return dp[V];
    }

};

class Solution {
public:
    unordered_map<char, vector<string>>hash;
    bool dfs(string& str, int pos) {
        if (pos == str.size())return true;
        bool ret = false;
        if (hash.count(str[pos]))
            for (auto& s : hash[str[pos]]) {
                if (s == str.substr(pos, s.size()))
                    ret |= dfs(str, pos + s.size());
            }
        return ret;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        for (auto& str : wordDict) {
            hash[*str.begin()].push_back(str);
        }
        return dfs(s, 0);
    }
};
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string>hash;
        for (auto& str : wordDict)hash.emplace(str);
        int sz = s.size();
        vector<bool>dp(sz + 1);
        dp[0] = true;
        s = ' ' + s;
        for (int i = 1; i <= sz; i++) {
            for (int j = i; j >= 1; j--) {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[sz];
    }
};
class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int sz = s.size();
        vector<int>dp(sz, 1);
        for (int i = 1; i < sz; i++) {
            if (s[i] - 1 == s[i - 1] || (s[i] == 'a' && s[i - 1] == 'z'))
                dp[i] = dp[i - 1] + 1;
        }
        int hash[26] = { 0 };
        for (int i = 0; i < sz; i++) {
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        }
        int ret = 0;
        for (auto el : hash)ret += el;
        return ret;
    }
};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int sz = nums.size();
        vector<int>dp(sz, 1);
        for (int i = 0; i < sz; i++) {
            int add = 0;
            for (int j = i; j >= 0; j--)
                if (nums[i] > nums[j])
                    add = max(add, dp[j]);
            dp[i] += add;
        }
        return *max_element(dp.begin(), dp.end());
    }
};
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int sz = nums.size(), ret = 0;
        vector<int>dp(sz, 1);
        for (int i = 0; i < sz; i++) {
            for (int j = i; j >= 0; j--)
                if (nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

#include<iostream>
using namespace std;

int main() {

    cout << 1 - pow(0.99, 500) - 5 * pow(0.99, 499);

    return 0;
}

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int sz = nums.size();
        vector<int> dp_gr(sz, 1);
        vector<int> dp_lr(sz, 1);
        for (int i = 1; i < sz; i++) {
            if (nums[i] > nums[i - 1]) {
                dp_lr[i] = max(dp_lr[i], dp_gr[i - 1] + 1);
                dp_gr[i] = dp_gr[i - 1];
            }
            else if (nums[i] < nums[i - 1]) {
                dp_gr[i] = max(dp_gr[i], dp_lr[i - 1] + 1);
                dp_lr[i] = dp_lr[i - 1];
            }
            else {
                dp_gr[i] = dp_gr[i - 1];
                dp_lr[i] = dp_lr[i - 1];
            }
        }
        return max(dp_gr[sz - 1], dp_lr[sz - 1]);
    }
};
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int sz = nums.size();
        vector<int>dp(sz, 1);
        vector<int>counts(sz, 1);
        int retLen = 1, retCount = 1;
        for (int i = 1; i < sz; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) {
                    if (dp[i] < dp[j] + 1) {
                        dp[i] = dp[j] + 1;
                        counts[i] = counts[j];
                    }
                    else if (dp[i] == dp[j] + 1) {
                        counts[i] += counts[j];
                    }
                }
            }
            if (dp[i] == retLen)retCount += counts[i];
            else if (dp[i] > retLen) {
                retLen = dp[i];
                retCount = counts[i];
            }
        }
        return retCount;
    }
};
#include <iostream>
#include <vector>
using namespace std;
int count(int a, int b) {
    while (b) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

int main() {
    long long int n, x;
    scanf("%lld %lld", &n, &x);
    vector<long long int>nums(n);
    for (int i = 0; i < n; i++)scanf("%lld", &nums[i]);
    for (auto num : nums) {
        x = x >= num ? x + num : x + count(num, x);
    }
    printf("%lld", x);
}
// 64 位输出请用 printf("%lld")
#include <functional>
#include <unistd.h>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型vector<vector<>>
     * @return int整型
     */
    int dx[2] = { 1,0 };
    int dy[2] = { 0,1 };
    int maxValue(vector<vector<int> >& grid) {
        // write code here
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>>values(m, vector<int>(n, -1));
        function<int(int, int)> dfs = [&](int x, int y) {
            if (values[x][y] != -1)return values[x][y];
            int ret = grid[x][y];
            for (int i = 0; i < 2; i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < m && b >= 0 && b < n)ret = max(ret, grid[x][y] + dfs(a, b));
            }
            values[x][y] = ret;
            return ret;
            };
        return dfs(0, 0);
    }
};
#include <iostream>
#include <utility>
#include <vector>
#include <string>
using namespace std;


int main() {
    int t = 0;
    scanf("%d", &t);
    while (t--) {
        int n = 0;
        scanf("%d", &n);
        vector<string>strs(n);
        string tmp;
        getline(cin, tmp);
        // cout << tmp << endl; 
        for (int i = 0; i < n; i++) { getline(cin, tmp); strs[i] = tmp; }
        // for(auto str: strs)cout << str << endl;
        int l = 0, r = n - 1, judge = 1;
        while (l < r) {
            int hash1[26] = { 0 };
            int hash2[26] = { 0 };
            string str1 = strs[l];
            string str2 = strs[r];
            for (auto c : str1)if (!hash1[c - 'a'])hash1[c - 'a']++;
            for (auto c : str2)if (!hash2[c - 'a'])hash2[c - 'a']++;
            int i = 0;
            for (i = 0; i < 26; i++)if (hash1[i] == 1 && hash2[i] == 1)break;
            if (i == 26) { judge = 0; break; }
            l++, r--;
        }
        if (!judge)printf("No\n");
        else printf("Yes\n");
    }

    return 0;
}
// 64 位输出请用 printf("%lld")
#include <iostream>
using namespace std;

int main() {
    long long int a, h, b, k;
    scanf("%lld %lld %lld %lld", &a, &h, &b, &k);
    long long int ret = 0;
    while (h > 0 && k > 0) {
        ret += a + b;
        k -= a;
        h -= b;
    }
    if (h > 0)ret += a * 10;
    if (k > 0)ret += b * 10;
    printf("%lld", ret);
}
// 64 位输出请用 printf("%lld")
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
using LL = long long int;

int main() {
    LL n;
    scanf("%lld", &n);
    vector<LL>nums(n);
    for (int i = 0; i < n; i++)scanf("%lld", &nums[i]);
    LL cur = -0x3f3f3f3f, ret = cur;
    for (auto& num : nums) {
        cur = max(cur + num, num);
        ret = max(ret, cur);
    }
    printf("%lld", ret);
}
// 64 位输出请用 printf("%lld")

#include<iostream>
#include<string>
using namespace std;
string str;
using LL = long long int;
LL func(LL sz) {
    bool flag = false;
    for (auto c : str)
        if (c != str[0]) { flag = true; break; }
    if (!flag)return 0;
    flag = false;
    int l = 0, r = sz - 1;
    while (l < r) {
        if (str[l] == str[r]) { l++, r--; }
        else { flag = true; break; }
    }
    if (!flag)return sz - 1;
    else return sz;
}
int main() {
    cin >> str;
    LL sz = str.size();
    cout << func(sz);
    return 0;
}   
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 0;
    scanf("%d", &n);
    int lr = 1, gr = n / 2 + 1;
    for (int i = 1; i <= n; i++) {
        if (i % 2)printf("%d ", gr++);
        else printf("%d ", lr++);
    }
}
// 64 位输出请用 printf("%lld")
#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    set<int>nums;
    for (int i = 0; i < n + m; i++) { int num; scanf("%d", &num); nums.emplace(num); }
    for (auto num : nums)cout << num << ' ';
    // vector<int>ret(nums.begin(),nums.end());
    // for(int i = 0;i < m + n - 1;i++)printf("%d ",ret[i]);
    // printf("%d",ret.back());

}
// 64 位输出请用 printf("%lld")
#include <iostream>
using namespace std;

int main() {
    int t = 0;
    scanf("%d", &t);
    while (t--) {
        int h, a, H, A;
        scanf("%d %d %d %d", &h, &a, &H, &A);
        if (a >= H || H <= 0 || A <= 0)printf("-1\n");
        else {
            int ret = 0, _H = H;
            while (h > 0) {
                _H -= a;
                if (_H <= 0) { _H = H; ret++; continue; }
                h -= A;
            }
            cout << ret << endl;
        }
    }
}
// 64 位输出请用 printf("%lld")
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    string tmp;
    unordered_set<string>con;
    while (n--) {
        cin >> tmp;
        sort(tmp.begin(), tmp.end());
        con.emplace(tmp);
    }
    printf("%d", con.size());
}
// 64 位输出请用 printf("%lld")
#include <climits>
#include <iostream>
using namespace std;

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    int ret = INT_MAX;
    for (int i = 0; i <= str2.size() - str1.size(); i++) {
        int _ret = 0;
        for (int j = 0; j < str1.size(); j++) {
            if (str1[j] != str2[i + j])_ret++;
        }
        ret = min(ret, _ret);
    }
    printf("%d", ret);
}
// 64 位输出请用 printf("%lld")
#include<iostream>
#include<vector>
using namespace std;
int dp[20010];
int main() {
    int v, n;
    scanf("%d", &v);
    scanf("%d", &n);
    vector<int>nums(n);
    for (int i = 0; i < n; i++)scanf("%d", &nums[i]);
    for (auto num : nums) {
        for (int i = v; i >= 0 && i >= num; i--) {
            dp[i] = max(dp[i], dp[i - num] + num);
        }
    }
    cout << v - dp[v];

    return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int N;
using LL = long long int;
int main() {
    scanf("%d", &N);
    vector<LL>nums(N);
    for (int i = 0; i < N; i++)scanf("%lld", &nums[i]);
    for (int i = 0; i < N - 1; i++) {
        int n1 = nums[i], n2 = nums[i + 1];
        if (n2 > n1)swap(n1, n2);
        if (n1 != n2 && (n1 / n2) % 2 != 0) { cout << "NO"; return 0; }
    }
    cout << "YES";
    return 0;
}
// 64 位输出请用 printf("%lld")
#include <iostream>
#include <vector>
using namespace std;
int N;
using LL = long long int;
int main() {
    scanf("%d", &N);
    vector<LL>nums(N);
    for (int i = 0; i < N; i++)scanf("%lld", &nums[i]);
    for (int i = 0; i < N - 1; i++) {
        int n1 = nums[i], n2 = nums[i + 1];
        if (n2 > n1)swap(n1, n2); //x = n1 / n2;if(x - (x & -x)) return false;
        if (n1 != n2 && (n1 / n2) % 2 != 0) {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}
// 64 位输出请用 printf("%lld")

#include <functional>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param m int整型vector<vector<>>
     * @return int整型
     */
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int citys(vector<vector<int> >& m) {
        // write code here
        int e = m.size(), f = m[0].size();
        vector<vector<bool>>mark(e, vector<bool>(f, false));
        function<void(int, int)>dfs = [&](int x, int y) {
            for (int k = 0; k < 4; k++) {
                int a = x + dx[k], b = y + dy[k];
                if (a >= 0 && a < e && b >= 0 && b < f && !mark[a][b] && m[a][b] == 1) {
                    mark[a][b] = true;
                    dfs(a, b);
                }
            }
            };
        int ret = 0;
        for (int i = 0; i < e; i++) {
            for (int j = 0; j < f; j++) {
                if (m[i][j] == 1 && !mark[i][j]) {
                    ret++;
                    mark[i][j] = true;
                    dfs(i, j);
                }
            }
        }
        return ret;
    }
};
#include <functional>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *t
     * @param m int整型vector<vector<>>
     * @return int整型
     */
    bool mark[201] = { 0 };
    int citys(vector<vector<int> >& m) {
        // write code here
        int n = m.size(), ret = 0;
        function<void(int)>dfs = [&](int a) {
            mark[a] = true;
            for (int i = 0; i < n; i++)
                if (m[a][i] && !mark[i])dfs(i);
            };
        for (int i = 0; i < n; i++) {
            if (!mark[i])dfs(i), ret++;
        }
        return ret;
    }
};
#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str;
    cin >> str;
    int len = str.size(), ret = 0;
    vector<vector<int>>dp(len, vector<int>(len));
    for (int i = len - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < len; j++) {
            if (str[i] == str[j])dp[i][j] = 2 + dp[i + 1][j - 1];
            else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    // for(auto& el : dp){
    //     for(auto & num :  el){
    //         cout << num << ' ';
    //     }
    //     cout << endl;
    // }
    cout << dp[0][len - 1];
}
// 64 位输出请用 printf("%lld")
#include <iostream>
#include <stdio.h>
int main() {
    std::cout << fprintf(stdout, "hello world%d\n",123) << std:: endl;

    return 0;
}
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <cstdlib>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    int judge(TreeNode* pRoot) {
        if (!pRoot) {
            return 0;
        }
        int left = judge(pRoot->left);
        int right = judge(pRoot->right);
        if (left == -1 || right == -1 || abs(left - right) > 1)return -1;
        return max(left, right) + 1;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        // write code here
        if (!pRoot)return true;
        int left = judge(pRoot->left);
        int right = judge(pRoot->right);
        if (left == -1 || right == -1)return false;
        return abs(left - right) <= 1;
    }
};
#include <stdio.h>
#include <signal.h>
#include <unistd.h>
int main()
class Solution {
public:
    long long calculateScore(vector<string>& instructions, vector<int>& values) {
        unordered_set<int>regr;
        long long int ret = 0, len = instructions.size();
        for (int i = 0; i >= 0 && i < len && regr.insert(i).second;) {
            if (instructions[i] == "add")ret += values[i++];
            else i += values[i];
        }
        return ret;
    }
};
class Solution {
public:
    int maximumPossibleSize(vector<int>& nums) {
        int back = nums[0], ret = 1, len = nums.size();
        for (int i = 1; i < len; i++) {
            if (nums[i] >= back) {
                back = nums[i];
                ret++;
            }
        }
        return ret;
    }
};

class Solution {
public:
    vector<long long> resultArray(vector<int>& nums, int k) {
        int len = nums.size();
        for (auto& num : nums)num %= k;
        vector<long long>ret(k);
        for (int i = 0; i < k; i++) {
            int pos = INT_MAX;
            for (int j = 0; j < len; j++) {
                if (nums[j] == i) {
                    int mul = 1, z = j;
                    for (; z < len; z++) {
                        mul *= nums[z];
                        if (mul % k == i)ret[i]++;
                    }
                    mul = nums[j], z = j - 1;
                    for (; z >= 0; z--) {
                        mul *= nums[z];
                        if (mul % k == i && z < pos)ret[i]++;
                    }
                    pos = min(pos, j);
                }
            }
        }
        return ret;
    }
}; ©leetcode
class Solution {
public:
    vector<long long> resultArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long>ans(k);
        vector f(n + 1, vector<int>(k));
        for (int i = 0; i < n; i++) {
            int v = nums[i] % k;
            f[i + 1][v] = 1;
            for (int j = 0; j < k; j++) {
                f[i + 1][v * j % k] += f[i][j];
            }
            for (int j = 0; j < k; j++) {
                ans[j] += f[i + 1][j];
            }
        }
        return ans;
    }
};
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    string nums;
    int cnt0 = 0, cnt1 = 0;
    cin >> nums;
    for (auto num : nums) {
        if (num == '0')cnt0++;
        else cnt1++;
    }
    //
//     printf("%d %d",cnt0,cnt1);
//     if(cnt1 % 2 || cnt0 % 2){
//         printf("0");
//         return 0;
//     }
    int l = 0, r = 0, len = n / 2;
    int _cnt0 = 0, _cnt1 = 0, ret = 0;
    while (l != n) {
        if (nums[r % n] == '1')_cnt1++;
        else _cnt0++;
        while (r - l + 1 == len) {
            if (_cnt0 == cnt0 / 2 && _cnt1 == cnt1 / 2)ret++;
            if (nums[l] == '1')_cnt1--;
            else _cnt0--;
            l++;
        }
        r++;
    }
    //
    printf("%d", ret);
    return 0;

}q
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 0;
    scanf("%d", &n);
    vector nums(n, vector<int>(n));
    for (auto& row : nums) {
        for (auto& col : row)
            scanf("%d", &col);
    }


    //
    vector f(n + 1, vector<int>(n + 1));
    vector f_row(n + 1, vector<int>(n + 1));
    vector f_col(n + 1, vector<int>(n + 1));
    int ret = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            f[i + 1][j + 1] = max(nums[i][j], nums[i][j] + f[i][j + 1] + f[i + 1][j]);
            f_row[i + 1][j + 1] = max(nums[i][j], nums[i][j] + f_row[i + 1][j]);
            f_col[i + 1][j + 1] = max(nums[i][j], nums[i][j] + f_col[i][j + 1]);
            ret = max(f[i + 1][j + 1], max(f_col[i + 1][j + 1], f_row[i + 1][j + 1]));
        }
    }
    //
    for (auto& row : nums) {
        for (auto& col : row)
            printf("%d ", col);
        printf("\n");
    }
    printf("#############\n");
    for (auto& row : f) {
        for (auto& col : row)
            printf("%d ", col);
        printf("\n");
    }

    // printf("%d",ret);
}
// 64 位输出请用 printf("%lld")
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
typedef long long ll;
ll a[N][N], sum[N][N], dp[N];
const ll inf = 1e18;
int main() {
    ios::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            sum[i][j] = sum[i - 1][j] + a[i][j];
        }
    }
    ll mx = -inf;
    for (int k1 = 1; k1 <= n; k1++) {
        for (int k2 = k1; k2 <= n; k2++) {
            for (int i = 1; i <= n; i++) {
                ll tmp = sum[k2][i] - sum[k1 - 1][i];
                dp[i] = max(dp[i - 1] + tmp, tmp);
                mx = max(mx, dp[i]);
            }
        }
    }
    printf("%lld", mx);
}
// 64 位输出请用 printf("%lld")
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 205;
int a[N][N], sum0[N][N], sum1[N][N], dp[N];
int main() {
    // ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int>ret(n + 1);
    for (int i = 1; i <= n; i++) {
        string tmp;
        cin >> tmp;
        for (int j = 1; j <= n; j++) {
            a[i][j] = tmp[j - 1] - '0';
            sum0[i][j] = sum0[i][j - 1];
            sum1[i][j] = sum1[i][j - 1];
            if (a[i][j])sum1[i][j]++;
            else sum0[i][j]++;
        }
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=n;j++){
    //         cout<<sum1[i][j]<<' ';
    //     }
    //     cout<<endl;
    // }

    for (int k = 1; k < n; k++) {//111111111
        for (int i = 1; i <= n - k; i++) {
            for (int j = 1; j <= n - k; j++) {
                int n0 = 0, n1 = 0;
                for (int z = 0; z <= k; z++) {
                    // cout <<"############"<<endl;
                    // cout <<sum0[z+i][j+k]<<' '<<sum0[i+z][j-1]<<endl;
                    // cout <<sum1[z+i][j+k]<<' '<<sum1[i+z][j-1]<<endl;
                    n0 += sum0[z + i][j + k] - sum0[i + z][j - 1];
                    n1 += sum1[z + i][j + k] - sum1[i + z][j - 1];
                }
                // cout<<n0<<' '<<n1<<endl;
                if (n0 == n1)ret[k + 1]++;
            }
        }
        // cout <<"@@@@@@@@@@@@@"<<endl;
    }
    for (int i = 1; i <= n; i++)cout << ret[i] << endl;
}
// 64 位输出请用 printf("%lld")
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    ll n, q, sum = 0;
    int cnt0 = 0;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        if (!num)cnt0++;
        sum += num;
    }
    while (q--) {
        ll l, r;
        cin >> l >> r;
        cout << sum + l * cnt0 << ' ' << sum + r * cnt0 << endl;
    }

}
// 64 位输出请用 printf("%lld")
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int cnt = 0;
    for (auto c : s)
        if (c == 'M' || c == 'T')cnt++;
    if (k >= n - cnt)cout << n;
    else cout << cnt + k;
}
// 64 位输出请用 printf("%lld")
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const ll N = 1e8 + 10;
ll a[10][10];
int main() {
    ios::sync_with_stdio(false);
    ll n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        ll u, v;
        cin >> u >> v;
        a[u][v] = 1;
        a[v][u] = 1;
    }
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= n; j++) {
            ll u = a[i][j];
            if (u == 0)continue;
            for (int k = 1; k <= n; k++)
                if (a[u][k])a[i][k] = 1;
        }
    }
    while (q--) {
        ll op, u, v;
        cin >> op >> u >> v;
        if (op == 1) {
            a[u][v] = 0;
            a[v][u] = 0;
        }
        else {
            if (a[u][v])cout << "Yes\n";
            else cout << "No\n";
        }
    }
}
// 64 位输出请用 printf("%lld")
#include <iostream>
int main() {

    int n = sqrt(6);
    std::cout << n << std::endl;
    return 0;
}
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param schedule int整型vector<vector<>>
     * @return bool布尔型
     */
    bool hostschedule(vector<vector<int> >& schedule) {
        // write code here
#define sch schedule
        int n = schedule.size();
        sort(schedule.begin(), schedule.end(), [&](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
            });
        for (int i = 0; i < n - 1; i++) {
            if (sch[i][1] > sch[i + 1][0])return false;
        }
        return true;
    }
};
#include <functional>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int n, sum = 0; cin >> n;
    vector<int>a(n);
    for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; }
    if (sum % 2) { cout << "false"; return 0; }
    function<bool(int, int)>dfs = [&](int b, int pos) {
        for (int i = pos + 1; i < n; i++) {
            if (b + a[i] == sum / 2)return true;
            if (b + a[i] > sum / 2)return false;
            if (dfs(b + a[i], pos + 1))return true;
        }
        return false;
        };
    bool ret = false;
    for (int i = 0; i < n; i++) {
        if (a[i] == sum / 2) { ret = true; break; }
        if (a[i] > sum / 2) { ret = false; break; }
        ret |= dfs(a[i], i);
        if (ret)break;
    }
    if (ret)cout << "true";
    else cout << "false";

}
// 64 位输出请用 printf("%lld")
#include <iostream>
int main() {
    printf("%lf\n", sqrt(11));
    std::cout << 11 % 2;

}
#include <bits/stdc++.h>
#include <cmath>
#include <iostream>
using namespace std;
const int inf = 0x4f4f4f4f;
int a[26];
bool judge(int num) {
    if (!num)return false;
    int tmp = sqrt(num);
    // cout<<tmp<<endl;
    for (int i = 2; i <= tmp; i++) {
        if (num % i == 0)return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    string str;
    cin >> str;
    int minn = inf, maxn = -inf;
    for (auto c : str) {
        int pos = c - 'a';
        a[pos]++;
        maxn = max(maxn, a[pos]);
        minn = min(minn, a[pos]);
    }
    if (judge(maxn - minn)) {
        cout << "Lucky Word\n";
    }
    else {
        cout << "No Answer\n";
    }
    cout << maxn - minn;
}
// 64 位输出请用 printf("%lld")
#endif // 0
#include <iostream>
using namespace std;
int main() {
    double sum = 2010.98;
    double sub = 437.5;
    double _sub1 = 19.9 + 33.9 + 13.9+22.9+27.9+9.7+23;
    double sub1 = 148.24;
    printf("杂费：%lf\n余费：%lf\n均费：%fl", sub1, sum - sub - sub1, (sum - sub - sub1)/31);
    /*
        洗衣液23
        袜子19.9
        牙刷22.9
        洗发水33.9
        臭肥皂13.9
        肥皂9.7
        牙膏27.9
        体恤
     */
}